package com.lzhsite.leetcode.algoritom.practise.string;
/**
 * 计算一组字符集合可以组成的回文字符串的最大长度
 * 409. Longest Palindrome (Easy)
 * Input : "abccccdd"
 * Output : 7
 * Explanation : 
 * One longest palindrome that can be built is "dccaccd", whose length is 7.
 * 使用长度为 256 的整型数组来统计每个字符出现的个数，每个字符有偶数个可以用来构成回文字符串。
 * 因为回文字符串最中间的那个字符可以单独出现，所以如果有单独的字符就把它放到最中
 * */

public class Longest_Palindrome {
	
	public int longestPalindrome(String s) {
	    int[] cnts = new int[256];
	    for (char c : s.toCharArray()) {
	        cnts[c]++;
	    }
	    int palindrome = 0;
	    for (int cnt : cnts) {
	        palindrome += (cnt / 2) * 2;
	    }
	    if (palindrome < s.length()) {
	        palindrome++;   // 这个条件下 s 中一定有单个未使用的字符存在，可以把这个字符放到回文的最中间
	    }
	    return palindrome;
	}
}
